Recurrence Relation
Q21.
Let T(n) be defined by T(1)=10 and T(n+1)=2n+T(n) for all integers n \geq 1. Which of the following represents the order of growth of T(n) as a function of n?Q22.
The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs isQ23.
When n=2^{2 k} for some k \geqslant 0, the recurrence relation T(n)=\sqrt{(} 2) T(n / 2)+\sqrt{n}, T(1)=1 evaluates to :Q24.
Let x_{n} denote the number of binary strings of length n that contain no consecutive 0s. The value of x_{5} isQ25.
The running time of an algorithm is represented by the following recurrence relation: T(n)=\left\{\begin{matrix} n & n\leq 3\\ T(\frac{n}{3})+cn& otherwise \end{matrix}\right. Which one of the following represents the time complexity of the algorithm?Q26.
Let x_{n} denote the number of binary strings of length n that contain no consecutive 0s. Which of the following recurrences does x_{n} satisfy?Q27.
Consider the following recurrence: T(n)=2T(\left \lceil \sqrt{n} \right \rceil)+ 1, T(1) = 1 Which one of the following is true?Q28.
Let T(n) be a function defined by the recurrence T(n) = 2T(n/2) + \sqrt n \text{ for }n \geq 2 and T(1) = 1 Which of the following statements is TRUE?Q30.
The recurrence relation T(1) = 2 T(n) = 3T (\frac{n}{4}) +n has the solution T(n) equal to